/*
 * @lc app=leetcode.cn id=4 lang=javascript
 *
 * [4] 寻找两个有序数组的中位数
 *
 * https://leetcode-cn.com/problems/median-of-two-sorted-arrays/description/
 *
 * algorithms
 * Hard (35.48%)
 * Likes:    1267
 * Dislikes: 0
 * Total Accepted:    70.1K
 * Total Submissions: 197.7K
 * Testcase Example:  '[1,3]\n[2]'
 *
 * 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
 * 
 * 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 * 
 * 你可以假设 nums1 和 nums2 不会同时为空。
 * 
 * 示例 1:
 * 
 * nums1 = [1, 3]
 * nums2 = [2]
 * 
 * 则中位数是 2.0
 * 
 * 
 * 示例 2:
 * 
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 * 
 * 则中位数是 (2 + 3)/2 = 2.5
 * 
 * 
 */
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
  let len = nums1.length + nums2.length
  let l = Math.floor((len + 1) / 2)
  let r = Math.floor((len + 2) / 2)
  if (l === r) return fn(nums1, nums2, l)
  return (fn(nums1, nums2, l) + fn(nums1, nums2, r)) / 2
};

function fn(arr1, arr2, k) {
  if (k === 1) {
    if (arr1.length) {
      if (arr2.length) return arr1[0] > arr2[0] ? arr2[0] : arr1[0]
      else return arr1[0]
    } else {
      return arr2[0]
    }
  }
  let p  = Math.floor(k / 2)
  let p1 = Math.min(p, arr1.length)
  let p2 = Math.min(p, arr2.length)

  if (p2 === 0 || arr1[p1 - 1] < arr2[p2 - 1]) {
    return fn(arr1.slice(p1), arr2, k - p1) // arr1去掉
  } else {
    return fn(arr1, arr2.slice(p2), k - p2) // arr2去掉
  }
}

// let re = findMedianSortedArrays([], [3, 4])

// console.log(re)

